1100F - Ivan and Burgers - CodeForces Solution

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue> 
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <ctime>
#include <assert.h>
#include <deque>
#include <list>
#define SEQ 19
 
using namespace std;
 
typedef pair<long long, int> pli;
typedef pair<long long , long long> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<int, long long > pil;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f, MID = 333, M = 1000086;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m, cnt, w[N];
vector<int> num;
ll res;

inline int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {  
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}

int lowbit(int x)
{
    return x & -x;
}
 
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
 
inline double rand(double l, double r)
{
    return (double)rand() / RAND_MAX * (r - l) + l;
}
 
inline ll qmi(ll a, ll b, ll c)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return res;
}
 
inline ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
inline double qmi(double a, ll b)
{
    double res = 1;
    while (b)
    {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
 
inline ll C(ll a, ll b)
{
    if (a < b) return 0;
    ll res = 1;
    for (ll i = 1, j = a; i <= b; i++, j--)
    {
        res = res * (j % MOD) % MOD;
        res = res * qmi(i, MOD - 2, MOD) % MOD;
    }
    return res;
}
 
inline int find(int x)
{
    return lower_bound(num.begin(), num.end(), x) - num.begin();
}

int e[N], ne[N], h[N], idx;
int p[500086][20];
int ft[500086][20];

inline void insert(int pos, int v, int nft) {
    if (!v) return;
    for (int i = 19; i > -1; i--)
        if ((v >> i) & 1) {
            if (!p[pos][i]) {
                p[pos][i] = v;
                ft[pos][i] = nft;
                break;
            }
            if (nft > ft[pos][i]) swap(nft, ft[pos][i]), swap(p[pos][i], v);
            v ^= p[pos][i];
        }
}

int main()
{
    cin >> n;
    for (int i = 1; i < n + 1; i++) scanf("%d", w + i);
    for (int i = 1; i < n + 1; i++) {
        for (int j = 0; j < 20; j++) p[i][j] = p[i - 1][j], ft[i][j] = ft[i - 1][j];
        insert(i, w[i], i);
    }
    cin >> m;
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int res = 0;
        for (int i = 19; i > -1; i--)
            if (ft[r][i] >= l)
                res = max(res, res ^ p[r][i]);
        printf("%d\n", res);
    }
    return 0;
}